package com.demo.example.hot100;

import java.util.ArrayList;
import java.util.List;

public class MergeTheInterval {
    public static void main(String[] args) {
        int[][] intervals=new int[][]{
                {1,3},
                {2,6},
                {8,10},
                {15,18}
        };
        merge(intervals);
    }
    public static int[][] merge(int[][] intervals){
        //合并区间
        if(intervals==null || intervals.length==0) {
            return new int[0][0];
        }
        //思考如何进行合并
        //最傻瓜的办法，用一个数组来模拟，最后进行一次遍历即可
        //先遍历一遍数组，找到interval中最大的数
        int max=Integer.MIN_VALUE;
        for(int i=0;i<intervals.length;i++){
                max=intervals[i][1]>max?intervals[i][1]:max;
        }
        //找到最大值后创建一个一维数组
        int[] array=new int[max+1];
        //会错题意了，可以稍作更改进行尝试
        boolean[] border=new boolean[max+1];
        //遍历二维数组，对这个辅助的一维数组进行填写
        for(int i=0;i<intervals.length;i++){
            //填写操作
            fillArray(array,intervals[i][0],intervals[i][1],border);
        }
        //todo: 进行遍历辅助数组，确定对应的返回区间，可以借助ArrayList进行辅助操作
        List<int[]> list=new ArrayList<>();
        //进行辅助数组的遍历，从0号位置开始遍历，出现的第一个，就记录为start,出现的最后一个end就记录为end
        int start=-1;
        int end=-1;
        for(int i=0;i<array.length;i++){
            if(array[i]==1 && start==-1){
                start=i;
            }
            if((array[i]==1 && array[i+1]==0) || (array[i]==1 && i==max)){
                end=i;
            }
            //找到end以后进行一个边界判断操作
            if(i!=max+1 && border[i]==true && border[i+1]==true){
                end=i;
            }
            //都不为-1，说明已经找到一个区间了
            if(start!=-1 && end!=-1){
                int[] tmp=new int[]{start,end};
                list.add(tmp);
                start=-1;
                end=-1;
            }
        }
        int[][] res=new int[list.size()][2];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        return res;
    }
    //写一个函数进行fill操作
    public static void fillArray(int[] array,int start,int end,boolean[] border){
        for(int i=start;i<=end;i++){
            array[i]=1; //填写操作
        }
        border[end]=true;
    }

}
